1. Field of the Invention
The present invention relates generally to determining cells for deletion in a network design.
2. Related Art
The development of newer generations of technologies has created an opportunity and requirement for wireless providers to upgrade their networks (e.g. 2nd generation to 3rd generation such as GSM to UMTS, IS-95 to cdma2000, etc.), while market forces require them to maximize the use of their capital and preexisting investments. Upgrades in technology not only offer additional services but also performance enhancements, which give an operator the opportunity to achieve comparable network wide coverage with fewer cells. In wireless communications systems, large geographical areas are segmented into many smaller areas, i.e., cells, each cell having its own radio transmitters and receivers and one or more controllers interconnected with a public switched telephone network (PSTN) for example. A network may be composed of a plurality of cells, each cell having a plurality of sectors, for example. The choice of which cells to be deleted from a network overlay to be used to effect the upgrade typically depends on planning and design of the network. A network overlay may be defined as new services or enhancement that can be implemented atop the existing network infrastructure to upgrade the existing network, for example (i.e., enhancements to upgrade a 2G network to a 3G network).
Although textbook networks are often configured in a perfect or ‘regular’ hexagonal array which achieves optimal coverage, such designs rarely, if ever, exist in actual networks. Designers must contend with many factors that make such regular arrays no longer optimal or possible when designing a network for initial deployment or network overlay.
For example, in actual networks, inhomogeneity is inherent. The influence of inhomogeneity on a real or actual network may be caused by terrain, non-uniform traffic distribution, clutter, and the need for site acquisition (real estate acquisition and zoning requirements significantly limit the set of potential cell sites), etc. In an inhomogeneous network, unlike an ideal or textbook network, the removal of a given cell in the network has different, and possibly undesirable, effects on the network. Accordingly, a problem in designing a network, either during site selection for initial network deployment (sometimes referred to as ‘greenfield’ deployment, where sites are considered for possible deletion to determine those sites which remain and that will eventually be deployed), or during network overlay when upgrading a network to a different technology, is to intelligently determine which cells to remove so that an operator may reduce the cell count of a network design with minimal, if any, performance penalty.
Current efforts have focused primarily on site selection of cells during initial network design and deployment, typically using simulated annealing techniques, and evolutionary algorithms, with little mention of using a greedy heuristic. In the greedy heuristic, all cells are evaluated on a cell-by-cell basis (one at a time) for possible deletion, and the cell with the lowest performance penalty is selected. Further deletions may be obtained by repeating the process and testing all remaining cells.
Like simulated annealing and genetic algorithms the greedy heuristic itself has computational difficulties. For example, in order to delete 1 of M cells, the greedy algorithm requires M separate evaluations, and hence M network simulations. Moreover, the aforementioned simulated annealing techniques, evolutionary algorithms and greedy heuristic algorithms have not focused on which cells to delete during a network overlay, and the site selection literature has only given superficial treatment to the role that inhomogeneity may play in network planning and design.